Basic arithmetic operations in modular arithmetic, that is, addition, subtraction, multiplication and modular inverse, where the modulus is prime, are a natural and inseparable part of cryptographic algorithms such as the encryption operation in RSA algorithms, of the cryptographic algorithms used in the U.S. Government Digital Signature Standard (NIST), and also of the nowadays often used cryptography that utilizes elliptic curves.
Multiplicative inverse in the finite field GF (p), where p is prime, is especially important in computing point operations over elliptic curves defined over a finite field GF (p) and in the acceleration of exponentiation operations.
The multiplicative inverse in a finite field GF (p), that is, the modular inverse of an integer q in [1, p−1] modulo p, where p is prime, is defined as the integer b in [1, p−1] such that it holds that q.b≡1 (mod p), often written as b=q−1 mod p. The most often used methods for generating the modular inverse are the so-called classical inverse according to Knuth, available in D. E. Knuth: “The Art of Computer Programming 2, Seminumerical Algorithms, Addison-Wesley, Reading, Mass. Third edition (1998)”, and the method based on the so-called Montgomery modular inverse, available in B. S. Kaliski Jr. “The Montgomery Inverse and Its Applications. IEEE Transaction on Computers 44 No. 8 (1995)”. Both of these methods are based on the Extended Euclidean Algorithm. They utilize binary operations of addition, subtraction and division or multiplication by two, where the operation of division by two or multiplication by two is actually a shift operation by one bit to the right or to the left applied to the binary representation of the operand.
These properties of both methods enable easy implementation in hardware.
When generating the so-called classical modular inverse, both even and odd values are continuously halved by shifting to the right according to the progress of the algorithm. This operation is performed in the following manner. If the value is odd, it is converted to an even value by adding the modulus p, which is prime and therefore odd, and then a right shift is performed. If a negative value appears during the computation due to subtraction, it is converted to a positive value by adding p; this represents an operation of converting a negative number to a positive number modulo p.
When generating the modular inverse using the Montgomery algorithm, the halving, that is the division by two performed in the course of the Euclidean algorithm, is postponed until the second phase of the algorithm. In this second phase, the halvings modulo p are performed, again by converting odd values to even values by adding p beforehand.
The above-mentioned methods of generating the modular inverse exhibit certain disadvantages. For the so-called classical generation, it is mainly a large number of “greater/less than” tests, which essentially represent subtraction operations. Whenever negative values appear, they are converted to positive values, and whenever odd values occur in the process of halving, they are converted to even values. Both operations again represent addition operations.
When generating the modular inverse using the Montgomery's method, the disadvantages are the redundant shift operations in the second phase of the process, the addition operation used for converting odd numbers to even numbers during the postponed halving in the second phase of the process, and a large number of “greater/less than” tests representing subtraction operations.